package com.yxp.util;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : yang.xp
 * @date : 2021/8/27 9:54
 * @description : 通过给定的广度遍历数组构建树
 */
public class BuildTreeByBfs {

    private int curIndex = 1;

    public static void main(String[] args) {
        BuildTreeByBfs buildTreeByBfs = new BuildTreeByBfs();
        int[] numbers = new int[]{5, 4, 8, 11, 0, 13, 4, 7, 2, 0, 0, 5, 1};

        TreeNode root = buildTreeByBfs.buildTree(numbers);
        System.out.println("--------------");
    }

    public TreeNode buildTree(int[] numbers) {
        TreeNode root = new TreeNode(numbers[0]);
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.add(root);
        while (!treeNodeQueue.isEmpty()) {
            if (curIndex >= numbers.length) {
                treeNodeQueue.clear();
                break;
            }
            treeNodeQueue.addAll(bfs(treeNodeQueue, numbers));
        }
        return root;
    }

    public Queue<TreeNode> bfs(Queue<TreeNode> treeNodeQueue, int[] numbers) {
        Queue<TreeNode> tempNodeQueue = new LinkedList<>();
        while (!treeNodeQueue.isEmpty()) {
            if (curIndex >= numbers.length) {
                tempNodeQueue.clear();
                break;
            }
            TreeNode poll = treeNodeQueue.poll();
            if (poll.val == 0) {
                continue;
            }
            poll.left = new TreeNode(numbers[curIndex++]);
            poll.right = new TreeNode(numbers[curIndex++]);
            tempNodeQueue.add(poll.left);
            tempNodeQueue.add(poll.right);
        }
        return tempNodeQueue;

    }

}
